package com;


import java.util.Arrays;

/**
 * 八皇后解法
 * 0 1 0 0 0 0 0 0 0
 * 0 0 0 1 0 0 0 0 0
 * 0 0 0 0 0 1 0 0 0
 * 1 0 0 0 0 0 0 1 0
 * 0 0 1 0 0 0 0 0 0
 * 0 0 0 0 1 0 0 0 0
 * 0 0 0 0 0 0 1 0 0
 * 0 0 0 0 0 0 0 0 1
 * <p>
 * 1 0 0 0 0 0 0 0 0
 * 0 0 1 0 0 0 0 0 0
 * 0 0 0 0 1 0 0 0 0
 * 0 0 0 0 0 0 1 0 0
 * 0 1 0 0 0 0 0 0 0
 * 0 0 0 1 0 0 0 0 0
 * 0 0 0 0 0 1 0 0 0
 * 0 0 0 0 0 0 0 1 0
 * <p>
 * 用下标表示     如果有11    那么  1*都不行     *1都不行   22 33 44 55 66 77 88都不行
 * 如果有23    那么
 * 1.横竖  2* *3 不行
 * 2.右斜  将23都加一   不行    34 45 56 78  减一也不行  12
 * 3.左斜    (32 41 14)不行    前加1 后减一  或 前减1   后减1
 * <p>
 * 回溯
 * <p>
 * 1.穷举法
 * 2.随机法
 */


public class EigthQueenAllPossible {
    static int sum = 0;

    public static void main(String[] args) {
        long begin = System.currentTimeMillis();

        //皇后的数量
        int N = 8;

        int[][] arr = new int[N][N];

        for (int[] ints : arr) {
            Arrays.fill(ints, 0);
        }

        read(0, arr);
        System.out.println(sum);
        System.out.println("总耗时:\t" + (System.currentTimeMillis() - begin) + "ms");
    }

    public static void read(int index, int[][] arr) {
        if (index >= arr[0].length) {
            /**
             * 这里可以将所有情况都打印出来
             */
            sum++;
            System.out.println("第" + sum + "种");
            for (int[] ints : arr) {
                for (int j = 0; j < arr.length; j++) {
                    System.out.print(ints[j] + "\t");
                }
                System.out.println();
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < arr[index].length; i++) {
            arr[index][i] = 1;
            if (rowAndList(arr, index, i) && xie(arr, index, i)) {
                read(index + 1, arr);
            }
            arr[index][i] = 0;
        }
    }

    /**
     * 判断行列是否可以
     *
     * @param x 行
     * @param y 列
     * @return 是否可以放
     */
    public static boolean rowAndList(int[][] arr, int x, int y) {
        arr[x][y] = 0;

        //判断行 行不行   int[x][i]
        for (int i = 0; i < arr.length; i++) {
            if (arr[x][i] == 1 || arr[i][y] == 1) {
                arr[x][y] = 1;
                return false;
            }
        }
        arr[x][y] = 1;
        return true;
    }

    /**
     * 判断斜是否可以
     * 参数是坐标
     *
     * @param x 行
     * @param y 列
     * @return 是否可以放
     */
    public static boolean xie(int[][] arr, int x, int y) {
//        a[3][2]
        arr[x][y] = 0;

        // 判断右斜 行不行   int[x][y]
        for (int i = 0; i < arr.length; i++) {

            if ((x + i) <= arr.length - 1 && (y + i) <= arr.length - 1) {
                if (arr[x + i][y + i] == 1) {
                    arr[x][y] = 1;
                    return false;
                }
            }
            if ((x - i) >= 0 && (y - i) >= 0) {
                if (arr[x - i][y - i] == 1) {
                    arr[x][y] = 1;
                    return false;
                }
            }

            if ((x + i) <= arr.length - 1 && (y - i) >= 0) {
                if (arr[x + i][y - i] == 1) {
                    arr[x][y] = 1;
                    return false;
                }
            }
            if ((x - i) >= 0 && (y + i) <= arr.length - 1) {
                if (arr[x - i][y + i] == 1) {
                    arr[x][y] = 1;
                    return false;
                }
            }
        }
        arr[x][y] = 1;
        return true;
    }
}
